A Thiessen polygon of a site, also called a Voronoi region, is the set of points that are closer to the site than to any of the other sites.

Let P = {p1, p2,…pn} be the set of sites and V = {v(p1), v(p2),…v(pn)} represent the Voronoi regions or Thiessen polygons for Pi,which is the intersection of all of the half planes defined by the perpendicular bisectors of pi and the other sites. Thus, a naïve method for constructing Thiessen Polygons can be formulated as follows:

Step 1 For each i such that i = 1, 2,…, n, generate n - 1 half planes H(pi,pj), 1 </= j </= n, i <> j, and construct their common intersection v(pi).

Step 2 Report V = {v(p1), v(p2),…v(pn)} as the output and stop.

This naïve procedure is, however, very inefficient for generating Thiessen polygons. The computation time increases exponentially as the number of sites increases. There are many other more competent methods for constructing a Thiessen polygon.